#include "train.h"


// 快排
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == NULL) return head;
        int l = head->val, r = head->val; // 最小值  最大值
        ListNode* p = head;
        while (p) //获取当前链表的最小值和最大值
        {
            l = min(p->val, l);
            r = max(p->val, r);
            p = p->next;
        }
        if (l == r) return head;
        int mid = (l + r) >> 1; //向下取整 ，/2 向0取整

        ListNode* h1 = nullptr, * h2 = nullptr;
        p = head;
        while (p) //头插法
        {
            ListNode* q = p->next; //头插法
            if (p->val <= mid)
            {
                p->next = h1;
                h1 = p;
            }
            else
            {
                p->next = h2;
                h2 = p;
            }
            p = q;
        }
        h1 = sortList(h1);
        h2 = sortList(h2);
        p = h1;
        while (p->next) p = p->next;
        p->next = h2;
        return h1;
    }
};







////归并排序
//class Solution {
//public:
//    int getLength(ListNode* head)
//    {
//        int n = 0;
//        while (head) {
//            n += 1;
//            head = head->next;
//        }
//        return n;
//    }
//    ListNode* merge_sort(ListNode* head, int n)
//    {
//        if (n <= 1) return head;
//        int l = n / 2, r = n - l; //左半部分长度 右半部分长度
//        ListNode* p = head;
//        for (int i = 1; i < l; i++) p = p->next; //找到左边部分最后一个结点
//        ListNode* p1 = head, *p2 = p->next;
//        p->next = NULL;
//        p1 = merge_sort(p1, l);
//        p2 = merge_sort(p2, r);
//
//        //合并有序链表
//        ListNode ret; //虚拟头节点
//        p = &ret, ret.next = NULL;
//        while (p1 || p2) {
//            if (p2 == NULL || p1 && p1->val <= p2->val)
//            {
//                p->next = p1;
//                p = p1;
//                p1 = p1->next;
//            }
//            else
//            {
//                p->next = p2;
//                p = p2;
//                p2 = p2->next;
//            }
//        }
//
//        //此时p指向第一个链表或者第二个链表的最后一个结点
//        return ret.next;
//
//
//    }
//    ListNode* sortList(ListNode* head) {
//        int n = getLength(head);
//        return merge_sort(head, n);
//    }
//};
